//
// Created by xili on 2024/9/4 9:24.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//暴力递归
class Solution1 {
public:
    int numDecodings(string s) {
        vector<int> v;
        for (auto &it: s) {
            v.push_back(it - '0');
        }
        return f(v, 0);
    }

    int f(vector<int> &v, int i) {
        if (i == v.size()) {
            return 1;
        }
        if (v[i] == 0) {
            return 0;
        }
        int ans = f(v, i + 1);
        if (i + 1 < v.size() && v[i] * 10 + v[i + 1] <= 26) {
            ans += f(v, i + 2);
        }
        return ans;
    }
};

//记忆化搜索
class Solution2 {
public:
    int numDecodings(string s) {
        vector<int> v;
        for (auto &it: s) {
            v.push_back(it - '0');
        }
        vector<int> dp(s.size(), -1);
        return f(v, dp, 0);
    }

    int f(vector<int> &v, vector<int> &dp, int i) {
        if (i == v.size()) {
            return 1;
        }
        if (v[i] == 0) {
            return 0;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        int ans = f(v, dp, i + 1);
        if (i + 1 < v.size() && v[i] * 10 + v[i + 1] <= 26) {
            ans += f(v, dp, i + 2);
        }
        dp[i] = ans;
        return ans;
    }
};

//严格位置依赖动态规划
class Solution3 {
public:
    int numDecodings(string s) {
        vector<int> v;
        for (auto &it: s) {
            v.push_back(it - '0');
        }
        int n = s.size();
        vector<int> dp(s.size() + 1);
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (v[i] == 0) {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                if (i + 1 < n && v[i] * 10 + v[i + 1] <= 26) {
                    dp[i] += dp[i + 2];
                }
            }
        }
        return dp[0];
    }
};

//滚动
class Solution4 {
public:
    int numDecodings(string s) {
        vector<int> v;
        for (auto &it: s) {
            v.push_back(it - '0');
        }
        int n = s.size();
        int next = 1;
        int nextNext = 0;
        int cur;
        for (int i = n - 1; i >= 0; i--) {
            if (v[i] == 0) {
                cur = 0;
            } else {
                cur = next;
                if (i + 1 < n && v[i] * 10 + v[i + 1] <= 26) {
                    cur += nextNext;
                }
            }
            nextNext = next;
            next = cur;
        }
        return next;
    }
};